Search Results

Documents authored by Ben Basat, Ran

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.25
How to Send a Real Number Using a Single Bit (And Some Shared Randomness)

Authors: Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We consider the fundamental problem of communicating an estimate of a real number x ∈ [0,1] using a single bit. A sender that knows x chooses a value X ∈ {0,1} to transmit. In turn, a receiver estimates x based on the value of X. The goal is to minimize the cost, defined as the worst-case (over the choice of x) expected squared error. We first overview common biased and unbiased estimation approaches and prove their optimality when no shared randomness is allowed. We then show how a small amount of shared randomness, which can be as low as a single bit, reduces the cost in both cases. Specifically, we derive lower bounds on the cost attainable by any algorithm with unrestricted use of shared randomness and propose optimal and near-optimal solutions that use a small number of shared random bits. Finally, we discuss open problems and future directions.
Cite as

Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik. How to Send a Real Number Using a Single Bit (And Some Shared Randomness). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ICALP.2021.25,
  author =	{Ben Basat, Ran and Mitzenmacher, Michael and Vargaftik, Shay},
  title =	{{How to Send a Real Number Using a Single Bit (And Some Shared Randomness)}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.25},
  URN =		{urn:nbn:de:0030-drops-140942},
  doi =		{10.4230/LIPIcs.ICALP.2021.25},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Shared Randomness, Distributed Protocols, Estimation, Subtractive Dithering}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.54
Approximate Query Processing over Static Sets and Sliding Windows

Authors: Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and multisets to support approximate versions of the operations rank(i) (i.e., computing sum_{j <= i} B[j]) and select(i) (i.e., finding min{p|rank(p) >= i}) queries. We study multiple types of approximations (allowing an error in the query or the result) and present lower bounds and succinct data structures for several variants of the problem. We also extend our model to sliding windows, in which we process a stream of elements and compute suffix sums. This is a generalization of the window summation problem that allows the user to specify the window size at query time. Here, we provide an algorithm that supports updates and queries in constant time while requiring just (1+o(1)) factor more space than the fixed-window summation algorithms.
Cite as

Ran Ben Basat, Seungbum Jo, Srinivasa Rao Satti, and Shubham Ugare. Approximate Query Processing over Static Sets and Sliding Windows. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 54:1-54:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ISAAC.2018.54,
  author =	{Ben Basat, Ran and Jo, Seungbum and Satti, Srinivasa Rao and Ugare, Shubham},
  title =	{{Approximate Query Processing over Static Sets and Sliding Windows}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{54:1--54:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.54},
  URN =		{urn:nbn:de:0030-drops-100027},
  doi =		{10.4230/LIPIcs.ISAAC.2018.54},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.34
Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log (W/epsilon)) lower bound for RW epsilon additive approximations and a Omega(log (W/epsilon)+log log R) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^(-1) log(RW)log log (RW)) space and performs updates in O(log (RW)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Give Me Some Slack: Efficient Network Measurements. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.MFCS.2018.34,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{34:1--34:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.34},
  URN =		{urn:nbn:de:0030-drops-96165},
  doi =		{10.4230/LIPIcs.MFCS.2018.34},
  annote =	{Keywords: Streaming, Network Measurements, Statistics, Lower Bounds}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.163
Brief Announcement: Give Me Some Slack: Efficient Network Measurements

Authors: Ran Ben Basat, Gil Einziger, and Roy Friedman

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of our paper [{Ben Basat} et al., 2017] is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0,1 ...,R} in a stream. While it is known that Omega(W log{R}) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log ({W/epsilon})) lower bound for RW epsilon additive approximations and a Omega(log ({W/epsilon})+log log{R}) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al., 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^{-1} log ({RW})log log ({RW})) space and performs updates in O(log ({RW})) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.
Cite as

Ran Ben Basat, Gil Einziger, and Roy Friedman. Brief Announcement: Give Me Some Slack: Efficient Network Measurements. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 163:1-163:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.ICALP.2018.163,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy},
  title =	{{Brief Announcement: Give Me Some Slack: Efficient Network Measurements}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{163:1--163:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.163},
  URN =		{urn:nbn:de:0030-drops-91672},
  doi =		{10.4230/LIPIcs.ICALP.2018.163},
  annote =	{Keywords: Streaming, Algorithms, Sliding window, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.11
Efficient Summing over Sliding Windows

Authors: Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of Omega(1/epsilon + log(W)) memory bits for Wepsilon-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/epsilon + log(W)) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0, 1, ..., R}, is addressed. The paper shows that approximating the sum within an additive error of RW epsilon can also be done using Theta(1/epsilon + log(W)) bits for epsilon = Omega(1/W). For epsilon = o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B = Theta(W*log(1/(W*epsilon))) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time.
Cite as

Ran Ben Basat, Gil Einziger, Roy Friedman, and Yaron Kassner. Efficient Summing over Sliding Windows. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{benbasat_et_al:LIPIcs.SWAT.2016.11,
  author =	{Ben Basat, Ran and Einziger, Gil and Friedman, Roy and Kassner, Yaron},
  title =	{{Efficient Summing over Sliding Windows}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.11},
  URN =		{urn:nbn:de:0030-drops-60241},
  doi =		{10.4230/LIPIcs.SWAT.2016.11},
  annote =	{Keywords: Streaming, Statistics, Lower Bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact